#include <vector>
using namespace std;
int trap(vector<int>& height) {
    int n = height.size();
    vector<int> max_l(n + 2);
    vector<int> max_r(n + 2);
    int ret = 0;
    for (int i = 1, j = n; i <= n; ++i, --j) {
        max_l[i] = max(max_l[i - 1], height[i - 1]);
        max_r[j] = max(max_r[j + 1], height[j - 1]);
    }
    for (int i = 1; i <= n; ++i) {
        int res = min(max_l[i - 1], max_r[i + 1]) - height[i - 1];
        res = max(0, res);
        ret += res;
    }
    return ret;
}
